1. Field of the Invention
This invention relates to digital processor systems, and in particular to methods and circuits for controlling the order of execution of operations to maximize processor performance.
2. Description of Related Art
A typical computer program is a list of instructions which when compiled or assembled generates a sequence of machine instructions or operations which a processor executes. The operations have a program order defined by the logic of the computer program and are generally intended for sequential execution in the program order. Scalar processors execute the operations in the program order which limits a scalar processor to completing one operation before completing the next operation. Superscalar processors contain a variety of execution units which operate in parallel to execute and complete multiple operations in parallel. Superscalar processors can therefore be faster than scalar processors operating at the same clock speed because superscalar processors can complete multiple operations per clock cycle while scalar processors ideally complete one operation per cycle.
A superscalar processor typically schedules execution of operations so that operations can be executed in parallel and complete out of the normal program order. Difficulties in out-of-order execution arise because one operation may depend on another in that the logic of a computer program requires that the first operation in the program be executed before the second operation. For example, whether an operation should be executed at all often depends on the result of a branch operation. Processors often predict the result of a branch operation before evaluating the branch operation and proceed with executing operations based on the prediction. The execution must be speculative because the branch prediction may have been incorrect so that the wrong operations were executed. Additionally, many computers require that a system's state be known just before or after an operation generates an error, interrupt, or trap; but when operations are executed out of order, an operation which follows an error in a program may have been executed before the error occurred. Thus, the processor must be able to undo operations which should not have been executed and must be able to construct the system's state following an error.
Superscalar architectures attempt to achieve several somewhat conflicting goals for scheduling operations. One goal is efficient scheduling to maximize parallel execution of operations which are actually required for completion of the program. Another goal is that scheduling circuitry not be overly complex because complexity increases the difficulty in providing a robust error free design and increases circuit size and cost. Still another goal is rapid scheduling so that a processor can operate at a high clock rate. Scheduling circuits which accomplish these goals are desired.